package cc.wsyw126.java.nowcoder.interview;

import cc.wsyw126.java.lintCode.convert_binary_search_tree_to_doubly_linked_list.TreeNode;
import cc.wsyw126.java.lintCode.swap_two_nodes_in_linked_list.ListNode;

import java.util.LinkedList;
import java.util.Queue;


/**
 * Created by Administrator on 2017/4/27.
 * 对于一棵二叉树，请设计一个算法，创建含有某一深度上所有结点的链表。
 * 给定二叉树的根结点指针TreeNode* root，以及链表上结点的深度，请返回一个链表ListNode，代表该深度上所有结点的值，请按树上从左往右的顺序链接，保证深度不超过树的高度，树上结点的值为非负整数且不超过100000。
 */
public class TreeLevel {
    public ListNode getTreeLevel(TreeNode root, int dep) {
        Queue<TreeNode> list = new LinkedList<>();
        TreeNode node = new TreeNode(0);
        list.add(root);
        list.add(node);
        int flag =1;
        while (!list.isEmpty()) {
            if (flag == dep) break;
            TreeNode poll = list.poll();
            if (poll==node) {
                if (list.isEmpty()) {
                    break;
                }
                list.add(node);
                flag++;
            }
            if (poll.left != null) list.add(poll.left);
            if (poll.right != null) list.add(poll.right);
        }
        list.remove(node);
        ListNode result = new ListNode(0);
        ListNode temp = result;
        while (!list.isEmpty()){
            temp.next=new ListNode(list.poll().val);
            temp=temp.next;
        }
        temp.next=null;
        return result.next;
    }
}
